package com.tree.BinaryTree;

public class BinaryTreeBaseOnArray {
	
	private String[] nodes;
	
	private int nodeCount;
	private int treeSize;
	private int treeDeep;
	public BinaryTreeBaseOnArray(int treeDeep) {
		super();
		this.treeDeep = treeDeep;
		System.out.println(Math.pow(2, treeDeep)-1);
		treeSize=(int) Math.pow(2, treeDeep)-1;
		nodes=new String[treeSize];
	}
	public BinaryTreeBaseOnArray(int treeDeep,String data) {
		super();
		this.treeDeep = treeDeep;
		System.out.println(Math.pow(2, treeDeep)-1);
		treeSize=(int) Math.pow(2, treeDeep)-1;
		nodes=new String[treeSize+1];
		nodes[++nodeCount]=data;
		
	}
	
	public boolean addLeft(String parent,String sonLeft){
		int indexFather=getNodeIndex(parent);
		if(indexFather!=0){
			int sonLeftIndex=indexFather*2;
			nodes[sonLeftIndex]=sonLeft;
			nodeCount++;
			return true;
		}
		return false;
	}
	public boolean addRight(String parent,String sonRight){
		int indexFather=getNodeIndex(parent);
		if(indexFather!=0){
			int sonRightIndex=indexFather*2+1;
			nodes[sonRightIndex]=sonRight;
			nodeCount++;
			return true;
		}
		return false;
	}
	
	private int getNodeIndex(String data){
		for (int i = 1; i <=nodes.length; i++) {
			if(nodes[i]!=null&&nodes[i].equals(data)){
				return i;
			}
		}
		return 0;
	}
	
	public String getParent(String node){
		int sonIndex=getNodeIndex(node);
		return nodes[sonIndex/2];
	}
	
	public String[] getChildren(String parent){
		
		int parentIndex=getNodeIndex(parent);
		if(parentIndex*2+1<treeSize){
			String[] children={nodes[parentIndex*2],nodes[parentIndex*2+1]};
			return children;
		}else{
			return null;
		}
	}
	
	public static void main(String[] args) {
		BinaryTreeBaseOnArray tree=new BinaryTreeBaseOnArray(3, "A");
		tree.addLeft("A", "B");
		tree.addRight("A", "C");
		tree.addLeft("B", "D");
		tree.addRight("B", "E");
		tree.addLeft("C", "F");
		for (String string : tree.nodes) {
			System.out.println(string);
		}
		
		System.out.println(tree.getParent("B"));
		String[] children=tree.getChildren("A");
		System.out.println(children[0]+children[1]);
	}
}
